Today's network links carry vast amounts of information. High bandwidth applications supported by these network links include, for example, streaming video, streaming audio, and large aggregations of voice traffic. In the future, network bandwidth demands are certain to increase. In order to meet such demands, one method that has been used is logical distribution of nodes in a network to subnetworks containing nodes that exchange a substantial amount of traffic. The larger a network becomes, the greater the demand to subdivide that network becomes. Network nodes such as routers and switches become more complex as greater numbers of line cards leading to each subdivided network or to other network nodes are contained in a router or switch.
FIG. 1 is a block diagram showing a topology of a network. Network nodes 130(1)-(M) are connected to a node 110. Each network node in FIG. 1 may take the form of a router, switch, bridge, hub, or other network node such as a compute or disk server. For purposes of explanation, nodes 110 and 120 will be referred to as routers, it being understood that nodes 110 and 120 are not limited thereto. The connections between nodes 130(1)-(M) and router 110 permit the nodes to share data. Router 110 is connected to router 120 through link 150. Router 120 is further connected to a plurality of network nodes 140(1)-(N).
Variable identifiers “M” and “N” are used in several instances in FIG. 1 to more simply designate the final element of a series of related or similar elements. Repeated use of such variable identifiers is not meant to imply a correlation between the sizes of such series of elements, although such correlation may exist. The use of such variable identifiers does not require that each series of elements has the same number of elements as another series delimited by the same variable identifier. Rather, in each instance of use, the variable identified by “M” or “N” may hold the same or a different value than other instances of the same variable identifier.
Routers 110 and 120 can handle communications between segments of a large network. Such a network communication node can be responsible for establishing and providing tens of thousands of network connections.
FIG. 2 is a block diagram illustrating an exemplary router (e.g., router 110). In this depiction, the router includes a number (N) of line cards (210(1)-(N)) that are communicatively coupled to a switch fabric 220, which is also communicatively coupled to a processor 230. Line cards 210(1)-(N) each include a port processor 212(1)-(N) that is controlled by a line card CPU 219(1)-(N). Each port processor 212(1)-(N) is also communicatively coupled to an ingress packet processor 214(1)-(N) and an egress packet processor 218(1)-(N). The ingress and egress packet processors are communicatively coupled to a switch fabric interface 216(1)-(N) that is also communicatively coupled to the switch fabric 220. Each line card CPU 219(1)-(N) is also coupled to switch fabric interface 216(1)-(N), ingress packet processor 214(1)-(N), and egress packet processor (1)-(N).
When a packet is received by a router such as that illustrated in FIG. 2, the router can process the packet in the following manner. Upon receipt at a port, a packet is sent from one of the port processors 212(1)-(N) corresponding to the port at which the packet was received to an ingress packet processor 214(1)-(N). An ingress packet processor can analyze the destination address of the packet to perform address lookups, as more fully set forth below. Once processed by an ingress packet processor, the packet can be sent through a switch fabric interface 216(1)-(N) to switch fabric 220. Switch fabric 220 can route the packet information to any line card 210(1)-(N) for egress processing according to the destination address of the packet. Once received by a line card switch fabric interface 216(1)-(N), a packet can be analyzed by an egress packet processor 218(1)-(N), as more fully set forth below, and subsequently sent out through a port processor 212(1)-(N).
Switch fabric 220 can be implemented using a technique appropriate to the implementation. Common switch fabric technologies are busses, crossbars, and shared memories. A crossbar switch fabric, for example, can be thought of as 2n busses linked by n*n crosspoints. If a crosspoint is on, data on an input bus corresponding to the crosspoint is made available to a corresponding output bus. A processor 230 or a scheduler must turn on and off crosspoints for each set of packets transferred across the crossbar. Alternatively, one input bus can drive several output busses by having each crosspoint on, to achieve multicast, either selectively or in a permanent state. Another switch fabric technology is an asynchronous transfer mode (ATM) switch fabric core in which a permanent virtual circuit is established from each port to each other port. Incoming IP packets are fragmented into ATM cells and switched through the switch fabric and then the ATM cells are reassembled into packets before transmission.
A router, such as that illustrated in FIG. 2, can have a large number of line cards coupled to the switch fabric. Unique addressing of each of N-line cards can be accomplished by using log2 N bits. For example, for 256 line cards, one needs eight bits to uniquely address each line card (log2 256=8). Such unique addressing can be found in unicast traffic.
Multicast routing protocols enable multicast transmission, i.e., one-to-many connections, by replicating packets close to the destination, obviating the need for multiple unicast connections for the same purpose, thereby saving network bandwidth and improving throughput. Similarly, within a router, multicast between line cards is enabled by a multicast capable switch fabric. A cell corresponding to an IP multicast packet is sent once from a source line card to the switch fabric, then the switch fabric sends the cell to all the destination line cards, obviating needless consumption of line card to switch fabric bandwidth resulting from multiple unicast cell transmissions for the same purpose. But multicast destination addressing to encompass every combination of destination line cards requires a bitmap destination address of a length equal to the number of line cards (e.g., N bits, so for the above example of 256 line cards, one needs a 256-bit destination address to be carried by each cell).
FIG. 3 is a simplified block diagram illustrating an example of packet processing that occurs within a router, such as that illustrated in FIG. 2. An ingress packet 310 arrives from a network connected to a line card 320 (line card 320 corresponds, for example, to one of line cards 210(1)-(N)). The ingress packet includes a destination address, along with other data such as the source of the packet and the substantive content of the packet. The illustrated destination address is a multicast address 315 formatted according to internet protocol (IP). In a network operating according to the multi-layer OSI network model, an IP packet such as that illustrated can be encapsulated in a lower level format packet, such as an ethernet packet. Line card 320 will remove encapsulation that is unnecessary to the operation of the router. The line card will then assign a destination label to the multicast address according to the results of a look up table (LUT) comparison performed by an ingress packet processor (e.g., 214(1)-(N)). LUT 325 contains a set of labels corresponding to prior received multicast addresses; such labels are internal to the router and only used in the context of the router. Line card 320 can then fragment the ingress packet into a number of cells 330 that (a) are of a length and format appropriate to the internal architecture of the router, and (b) each contain the label 335 generated from LUT 325. Such fragmentation can be performed, for example, in a switch fabric interface 216(1)-(N).
Cell 330 is then passed to the router switch fabric 340, wherein the cell is directed to appropriate egress ports. A single multicast cell can have multiple destination egress ports. Switch fabric 340 will duplicate multicast cells and direct them to the appropriate destination ports, such operations being performed by a processor associated with the switch fabric (e.g., 230). The switch fabric can determine the destination egress ports for a cell by referencing a Label to Destination Table (LTDT) 345. LTDT 345 can contain an entry for each label, wherein an entry includes a bitmap of the egress ports from the switch fabric and reference to the bitmap provides information as to which switch egress ports the cell must be directed. Each label bitmap is a switch destination address 350. Once duplicated and sent through switch fabric 340, cells exit the switch fabric and are sent to egress line cards 360(1)-(X) that are coupled to corresponding switch egress ports. The egress line cards can then remove the cell label and reconstruct the original packet in preparation for transmission on networks connected to the egress line cards (such an operation can be performed by, for example, switch fabric interface 216(1)-(N)). An egress packet processor (e.g., 218(1)-(N)) on the egress line card can perform another address lookup to determine whether the egress line card should duplicate a packet for multiple multicast subscribers. A port processor (e.g., 212(1)-(N)) on an egress line card will encapsulate the outgoing packet in an appropriate form for the attached network.
As stated above, the more destination line cards that are present in a router, the longer a switch fabric destination address will need to be in order to uniquely address each multicast address combination. To have such a long destination address in each cell transmitted by a switch fabric will result in wasted space in each cell transported through the switch fabric (since, for example, a unicast cell, in a 256 line card router, need only 8 bits for a unique address versus 256 bits for a multicast destination address). The more line cards present in a router, the more bandwidth consumed by switching such large destination addresses.
Rather than provide a destination address that contains enough bits to uniquely address every multicast combination, and therefore wasting switch fabric bandwidth, an address field of a length between log2N (a unicast address length) and N (a multicast bitmap length) can be chosen. Such a shorter destination address field will not be able to uniquely address every combination of addresses directed to the N line cards. Over time, the number of multicast destinations that will need to be supported by the switch fabric will increase. Therefore, for several multicast destinations, the router switch will have to engage in “supercasting”, wherein a multicast packet will ultimately be sent not only to subscribing line cards but also to one or more non-subscribing line cards that will ultimately drop the multicast packet.
Supercasting conserves bandwidth from a line card to the switch fabric by decreasing the length of the destination address field of cells being transferred within the router switch fabric. But during supercasting, bandwidth from a switch fabric to attached line cards will be wasted due to the transmission of cells to nonsubscribing line cards. Further, bandwidth-impacting inefficiencies also occur at the nonsubscribing line cards as processing must occur in the line cards in order to drop the packets.
What is therefore desired is a method of assigning destination addresses for multicast cells in a manner so that the amount of supercast, that is the amount of wasted bandwidth, is minimized, and thereby maximizing the useful throughput of the router.